//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 示例1： 
//
// 
//
// 
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
// 
//
// 示例2： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
// 
//
// 示例3： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 100] 
// 0 <= node.val <= 9 
// 输入数据保证链表代表的数字无前导 0 
// 
//
// 
//
// 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。 
// Related Topics 栈 链表 数学 
// 👍 439 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Stack;

public class AddTwoNumbersIi {
    public static void main(String[] args) {
        ListNode h14 = new ListNode(3);
        ListNode h13 = new ListNode(4,h14);
        ListNode h12 = new ListNode(2,h13);
        ListNode h11 = new ListNode(7,h12);

        ListNode h23 = new ListNode(4);
        ListNode h22 = new ListNode(6,h23);
        ListNode h21 = new ListNode(5,h22);

        ListNode ans = new AddTwoNumbersIi().new Solution().addTwoNumbers(h11, h21);

    }
    public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1;

        /*ListNode reverse1 = new ListNode(l1.val, null);//新建的头结点
        ListNode temp = l1;
        ListNode temp2;
        while (temp != null){
            temp2 = reverse1.next;
            reverse1.next = new ListNode(temp.val);
            reverse1.next.next = temp2;
            temp = temp.next;
        }
        reverse1 = reverse1.next;

        ListNode reverse2 = new ListNode(l2.val, null);//新建的头结点
        temp = l2;
        while (temp != null){
            temp2 = reverse2.next;
            reverse2.next = new ListNode(temp.val);
            reverse2.next.next = temp2;
            temp = temp.next;
        }
        reverse2 = reverse2.next;


        ListNode p = new ListNode(-1);
        ListNode tempP;
        int sum = 0;
        boolean flag = false;
        while (reverse1 !=null && reverse2!=null){
            tempP = p.next;
            if (!flag) sum = reverse1.val + reverse2.val;
            else {
                sum = reverse1.val + reverse2.val + p.next.val;
                if (sum >= 10){
                    tempP.val = sum - 10;
                    p.next = new ListNode(1,tempP);
                    flag = true;
                }else {
                    p.next.val = sum;
                    flag = false;
                }
                reverse1 = reverse1.next;
                reverse2 = reverse2.next;
                continue;
            }
            if (sum>=10){
                ListNode node = new ListNode(sum - 10, tempP);
                p.next = new ListNode(1,node);
                flag = true;
            }else {
                p.next = new ListNode(sum,tempP);
            }
            reverse1 = reverse1.next;
            reverse2 = reverse2.next;
        }
        reverse1 = reverse1 == null ? reverse2: reverse1;
        while (reverse1!=null){
            tempP = p.next;
            if (flag){
                sum = reverse1.val + p.next.val;
                if (sum >= 10){
                    tempP.val = sum - 10;
                    p.next = new ListNode(1,tempP);
                    flag = true;
                }else {
                    p.next.val = sum;
                    flag = false;
                }
                reverse1 = reverse1.next;
                continue;
            }
            p.next = new ListNode(reverse1.val);
            p.next.next = tempP;
            reverse1 = reverse1.next;
        }
        return p.next;*/
        /**
         * 记住了，只要和反转有关的，都用栈来解决
         * 这样就得到了两个逆序的链表
         */
        Stack<Integer> stack1 = new Stack<>();
        while (l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        Stack<Integer> stack2 = new Stack<>();
        while (l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;//保存进位值
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry>0){//这里必须加上进位>0的条件，不然会少数值
            int sum = carry;
            sum += stack1.isEmpty() ? 0 : stack1.pop();
            sum += stack2.isEmpty() ? 0 : stack2.pop();
            ListNode node = new ListNode(sum % 10);//新建一个节点
            //这两个指向是真的秀
            node.next = head;//向首位添加节点
            head = node;//指向了首位
            carry = sum/10;
        }
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}